package com.优先队列.练习题;



import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Leetcode23 {
    /**
     * 合并多个有序链表
     *
     * 给你一个链表数组，每个链表都已经按升序排列。
     *
     * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
     *
     *
     *
     * 示例 1：
     *
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     */
    public ListNode mergeKLists(ListNode[] lists){
        PriorityQueue<ListNode> queue =
                new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(node);
            }
        }
        ListNode s = new ListNode(-1,null);
        ListNode p = s;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = node;
            if (p.next != null) {
                queue.offer(p.next);
            }
        }
        return s.next;
    }




}
